Shattering Thresholds for Random Systems of Sets, Words, and Permutations

摘要

This paper considers a problem that relates to the theories of coveringarrays, permutation patterns, Vapnik-Chervonenkis (VC) classes, and probabilitythresholds. Specifically, we want to find the number of subsets of[n]:={1,2,....,n} we need to randomly select, in a certain probability space,so as to respectively "shatter" all t-subsets of [n]. Moving from subsets towords, we ask for the number of n-letter words on a q-letter alphabet that areneeded to shatter all t-subwords of the q^n words of length n. Finally, weexplore the number of random permutations of [n] needed to shatter(specializing to t=3), all length 3 permutation patterns in specifiedpositions. We uncover a very sharp zero-one probability threshold for theemergence of such shattering; Talagrand's isoperimetric inequality in productspaces is used as a key tool.